package SGEngine

import (
	//"fmt"
	"math"
)

type PackRect struct {
	X      int
	Y      int
	Width  int
	Height int
}

const (
	BinPack_ContactPoint = 0
)

type MaxRectsBinPack struct {
	BinWidth       int
	BinHeight      int
	AllowRotations bool
	score1         int
	score2         int
	UsedRectangles []PackRect
	FreeRectangles []PackRect
}

func (m *MaxRectsBinPack) Init(_width int, _height int, _allowrotations bool) {
	m.BinWidth = _width
	m.BinHeight = _height
	m.AllowRotations = _allowrotations
	MaxRect := PackRect{0, 0, _width, _height}
	m.FreeRectangles = append(m.FreeRectangles, MaxRect)
}

func (m *MaxRectsBinPack) Insert(_width int, _height int, _type int) PackRect {
	var NewNode PackRect
	m.score1 = 0
	m.score2 = 0
	switch _type {
	case 0:
		NewNode = m.FindPositionForNewNodeContactPoint(_width, _height, m.score1)
	}

	if NewNode.Height == 0 {

		return NewNode
	}
	NumRectAnglesToProcess := len(m.FreeRectangles)
	for i := 0; i < NumRectAnglesToProcess; i++ {
		if m.SplitFreeNode(m.FreeRectangles[i], NewNode) {
			m.RemoveI(i)
			i = i - 1
			NumRectAnglesToProcess = NumRectAnglesToProcess - 1
		}
	}
	m.PruneFreeList()
	m.UsedRectangles = append(m.UsedRectangles, NewNode)
	return NewNode
}

func (m *MaxRectsBinPack) FindPositionForNewNodeContactPoint(_width, _height, bestContactScore int) PackRect {

	var BestNode PackRect
	bestContactScore = -1

	for i := 0; i < len(m.FreeRectangles); i++ {
		if m.FreeRectangles[i].Width >= _width && m.FreeRectangles[i].Height >= _height {
			score := m.ContactPointScoreNode(m.FreeRectangles[i].X, m.FreeRectangles[i].Y, _width, _height)
			if score > bestContactScore {
				BestNode.X = m.FreeRectangles[i].X
				BestNode.Y = m.FreeRectangles[i].Y
				BestNode.Width = _width
				BestNode.Height = _height
				bestContactScore = score
			}
		}

		if m.AllowRotations && m.FreeRectangles[i].Width >= _height && m.FreeRectangles[i].Height >= _width {

			score := m.ContactPointScoreNode(m.FreeRectangles[i].X, m.FreeRectangles[i].Y, _height, _width)
			if score > bestContactScore {
				BestNode.X = m.FreeRectangles[i].X
				BestNode.Y = m.FreeRectangles[i].Y
				BestNode.Width = _height
				BestNode.Height = _width
				bestContactScore = score
			}
		}
	}

	return BestNode
}

func (m *MaxRectsBinPack) ContactPointScoreNode(x, y, _width, _height int) int {
	score := 0
	if x == 0 || x+_width == m.BinWidth {
		score += _height
	}

	if y == 0 || y+_height == m.BinHeight {
		score += _width
	}

	for i := 0; i < len(m.UsedRectangles); i++ {
		if m.UsedRectangles[i].X == x+_width || m.UsedRectangles[i].X+m.UsedRectangles[i].Width == x {
			score += m.CommonIntervalLength(m.UsedRectangles[i].Y, m.UsedRectangles[i].Y+m.UsedRectangles[i].Height, y, y+_height)
		}

		if m.UsedRectangles[i].Y == y+_height || m.UsedRectangles[i].Y+_height == y {
			score += m.CommonIntervalLength(m.UsedRectangles[i].X, m.UsedRectangles[i].X+m.UsedRectangles[i].Width, x, x+_width)
		}
	}

	return score
}

func (m *MaxRectsBinPack) CommonIntervalLength(i1start, i1end, i2start, i2end int) int {
	if i1end < i2start || i2end < i1start {
		return 0
	}
	return int(math.Min(float64(i1end), float64(i2end)) - math.Max(float64(i1start), float64(i2start)))
}

func (m *MaxRectsBinPack) SplitFreeNode(freeNode, usedNode PackRect) bool {
	if usedNode.X >= freeNode.X+freeNode.Width || usedNode.X+usedNode.Width <= freeNode.X || usedNode.Y >= freeNode.Y+freeNode.Height || usedNode.Y+usedNode.Height <= freeNode.Y {
		return false
	}
	if usedNode.X < freeNode.X+freeNode.Width && usedNode.X+usedNode.Width > freeNode.X {
		if usedNode.Y > freeNode.Y && usedNode.Y < freeNode.Y+freeNode.Height {
			var newNode PackRect
			newNode.Height = usedNode.Y - newNode.Y
			m.FreeRectangles = append(m.FreeRectangles, newNode)
		}

		if usedNode.Y+usedNode.Height < freeNode.Y+freeNode.Height {
			newNode := freeNode
			newNode.Y = usedNode.Y + usedNode.Height
			newNode.Height = freeNode.Y + freeNode.Height - (usedNode.Y + usedNode.Height)
			m.FreeRectangles = append(m.FreeRectangles, newNode)
		}
	}

	if usedNode.Y < freeNode.Y+freeNode.Height && usedNode.Y+usedNode.Height > freeNode.Y {
		if usedNode.X > freeNode.X && usedNode.X < freeNode.X+freeNode.Width {
			newNode := freeNode
			newNode.Width = usedNode.X - newNode.X
			m.FreeRectangles = append(m.FreeRectangles, newNode)
		}
		if usedNode.X+usedNode.Width < freeNode.X+freeNode.Width {
			newNode := freeNode
			newNode.X = usedNode.X + usedNode.Width
			newNode.Width = freeNode.X + freeNode.Width - (usedNode.X + usedNode.Width)
			m.FreeRectangles = append(m.FreeRectangles, newNode)
		}
	}
	return true
}

func (m *MaxRectsBinPack) PruneFreeList() {
	for i := 0; i < len(m.FreeRectangles); i++ {
		for j := i + 1; j < len(m.FreeRectangles); j++ {
			if m.isContainedIn(m.FreeRectangles[i], m.FreeRectangles[j]) {
				m.RemoveI(i)
				break
			}

			if m.isContainedIn(m.FreeRectangles[j], m.FreeRectangles[i]) {
				m.RemoveI(j)
			}
		}
	}
}

func (m *MaxRectsBinPack) isContainedIn(a, b PackRect) bool {
	return a.X >= b.X && a.Y >= b.Y && a.X+a.Width <= b.X+b.Width && a.Y+a.Height <= b.Y+b.Height
}

func (m *MaxRectsBinPack) RemoveI(i int) {
	numMoved := len(m.FreeRectangles) - i - 1
	if numMoved <= 0 {
		return
	}
	copy(m.FreeRectangles[i:len(m.FreeRectangles)-1], m.FreeRectangles[i+1:len(m.FreeRectangles)])
	m.FreeRectangles = m.FreeRectangles[:len(m.FreeRectangles)-1]
}
